---
title: "L2-002 链表去重"
created: 2025-11-28
tags:
  - 算法
---

# L2-002 链表去重

## 题目 [L2-002 链表去重](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805072641245184&page=1)

![[image-b3946cfa.png]]

## 思路分析

![[image-fbd3c515.png]]

尽力了孩子们 康复训练下马威 绞尽脑汁回忆起模拟链表怎么写

![[image-39f0e16a.png]]

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

unordered_map<int,PII> node;
unordered_map<int,PII> del_node;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int head,n;cin>>head>>n;

	while(n--){
		int idx,var,next;cin>>idx>>var>>next;
		node[idx]={var,next};
	}

	set<int> have_exist;
	del_node[-1]={0,-1};
	int curDelNail=-1;
	for(int i=head;i!=-1;i=node[i].second){
//		cout<<node[i].first<<endl;
		// 因为需要删除节点 更改next域 如果走到该点发现要删除 需要索引回上一个点
		// 三种办法
		// 一：更改结构 记录上一个节点的地址
		// 二：用一个前驱先一步去探
		// 三：借尸还魂 把下一个的值全拷过来 把下一个删掉 这样链不会出问题 但这里不适用 本质地址没变 结果要输出该点的地址
		// 改结构太麻烦了 还是用第二种吧 用一个先锋去探下一个位置要不要删

		have_exist.insert(abs(node[i].first)); //因为是看下一个点删不删 所以先要把当前点放进去

		int pre = node[i].second;
		if(have_exist.find(abs(node[pre].first))!=have_exist.end()){
//			node[i].second=node[pre].second;

			// 删除的节点又要形成一个新链表 怎么处理
			// 又要是尾插法  留个尾巴在这 等着赋值？
			del_node[curDelNail].second = node[i].second;
			del_node[node[i].second]={node[pre].first,-1};
			curDelNail=node[i].second;

			node[i].second=node[pre].second;
		}
	}

	for(int i=head;i!=-1;i=node[i].second){
		printf("%05d %d %d\n",i,node[i].first,node[i].second);
	}

	for(int i=del_node[-1].second;i!=-1;i=del_node[i].second){
		printf("%05d %d %d\n",i,del_node[i].first,del_node[i].second);
	}

	return 0;
}
```

## 代码实现

原链表的node已经存储了所有节点，无需新开del_node单独存储删除的节点，直接复用node结构，用del_head和del_tail维护删除链表的头和尾。

在处理当前节点时检查下一个节点是否需要删除，但此时当前节点的next可能已被修改，导致循环跳过节点。 （1→2→3→4   2被删除
 1→3→4  走到3 看下一步4要不要删 而3被忽略了检查 所以还是得记录前驱节点 检查当前节点）

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

unordered_map<int,PII> node;

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int head,n;cin>>head>>n;

	while(n--){

		int idx,var,next;cin>>idx>>var>>next;

		node[idx]={var,next};

	}

	set<int> seen_abs;

	int del_head = -1, del_tail = -1;

	int prev = -1; // 前驱节点地址

    int curr = head; // 当前节点地址

	while(curr!=-1){

        int curr_abs=abs(node[curr].first);

        if (seen_abs.count(curr_abs)) {

            // 需要删除当前节点

            if (prev != -1) {

                node[prev].second = node[curr].second; // 前驱跳过当前节点

            } else {

                head = node[curr].second; // 更新头节点

            }

            // 将当前节点加入删除链表

            if (del_head == -1) {

                del_head = del_tail = curr;

            } else {

                node[del_tail].second = curr;

                del_tail = curr;

            }

            node[curr].second = -1; // 断开原有连接

            curr = node[prev].second; // 移动到下一个节点

        } else {

            seen_abs.insert(curr_abs);

            prev = curr;

            curr = node[curr].second;

        }

    }

	for(int i=head;i!=-1;i=node[i].second){

		printf("%05d %d ", i, node[i].first);

        if (node[i].second == -1) printf("-1\n");

        else printf("%05d\n", node[i].second);

	}

	for(int i=del_head;i!=-1;i=node[i].second){

		printf("%05d %d ", i, node[i].first);

        if (node[i].second == -1) printf("-1\n");

        else printf("%05d\n", node[i].second);

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-001 紧急救援|L2-001 紧急救援]] 🏠 [[00-天梯赛]] ➡️ [[L2-003 月饼|L2-003 月饼]]